﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    public class PermutationAndCombination<T>
    {
        public List<List<T>> GetCombination(List<T> source, int getNum)
        {
            List<List<T>> ls = new List<List<T>>();

            if (source.Count < getNum)
            {
                throw new Exception();
            }

            List<T> currentItem;

            List<T> firstItem = new List<T>();
            firstItem.AddRange(source.Take(getNum));

            List<T> lastItem = new List<T>();
            lastItem.AddRange(source.Skip(source.Count - getNum).Take(getNum));

            ls.Add(firstItem);

            currentItem = firstItem;

            while (!IsReachLastItem(currentItem, lastItem))
            {
                var nextItem = GetNextItem(source, currentItem);
                ls.Add(nextItem);
                currentItem = nextItem;
            }

            return ls;
        }

        private bool IsReachLastItem(List<T> currentItem, List<T> LastItem)
        {
            for (int i = 0; i < currentItem.Count; i++)
            {
                if (!currentItem[i].Equals(LastItem[i]))
                {
                    return false;
                }
            }

            return true;
        }

        private List<T> GetNextItem(List<T> source, List<T> currentItem)
        {
            List<T> result = new List<T>();
            int workPosition = currentItem.Count - 1;

            while (source.IndexOf(currentItem[workPosition]) == (source.Count - 1) - (currentItem.Count - 1 - workPosition))
            {
                workPosition--;
            }

            if (workPosition == -1)
            {
                return null;
            }
            else
            {
                // divide the position into three parts. 
                // part 1 the values should not be changed.
                // part 2 the current work index value should be increased.
                // part 3 the next position should be set to 

                // the value should not be changed
                for (int i = 0; i < workPosition; i++)
                {
                    result.Add(currentItem[i]);
                }

                // current work index value should be increased.
                var workSourceIndex = source.IndexOf(currentItem[workPosition]);
                result.Add(source[workSourceIndex + 1]);

                // The next position value should be set to minValue(But this value is bigger than preious position value), if position value has been changed.
                for (int i = 0; i < currentItem.Count - 1 - workPosition; i++)
                {
                    result.Add(source[workSourceIndex + 2 + i]);
                }
            }

            return result;
        }
    }
}
